package com.aqie.easy.bitOperation;

import edu.princeton.cs.algs4.In;

import java.util.ArrayList;
import java.util.List;

/**
 * 401 二进制手表 todo
 * 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间
 * 小时不以0开头
 */
public class ReadBinaryWatch {
    /**
     * 1, 2ms
     * @param num
     * @return
     */
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++){
            for (int j = 0; j < 60; j++){
                if (Integer.bitCount(i) + Integer.bitCount(j) == num){
                    String tmp = j < 10 ? "0"+j : j+"";
                    res.add(i+":"+tmp);
                }
            }
        }
        return res;
    }

    /**
     * 2. 回溯
     * @param num
     * @return
     */
    public List<String> readBinaryWatch2(int num) {
        List<String> lists = new ArrayList<>();
        if(num>=9)return lists;
        int[] nums2 = new int[6];
        getNums(nums2);
        dfs(nums2, lists, 0,0, 0, num);
        return lists;
    }

    private void dfs(int[] nums, List<String> lists, int index, Integer l1, Integer l2, int num) {
        if (num == 0) {
            if(l1>=12||l2>=60)return;
            lists.add(l1 + ":" + String.format("%02d", l2));
        } else {
            for (int i = index; i < 10; i++) {
                if (i < 6) {
                    l2+=nums[i];
                    dfs(nums, lists, i + 1, l1, l2, num - 1);
                    l2-=nums[i];
                } else {
                    l1+=nums[i - 6];
                    dfs(nums, lists, i + 1, l1, l2, num - 1);
                    l1-=nums[i - 6];
                }
            }
        }
    }

    private void getNums(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = 1 << i;
        }
    }

    public static void main(String[] args) {
        // 1. 计算二进制1的个数
        int num = 3;
        System.out.println(Integer.bitCount(num));
    }
}
